def get_prime(n):
    not_prime = [0] * (n+1)
    prime = []
    for i in range(2, n+1):
        if not_prime[i] == 0:
            prime.append(i)
            for j in range(2 * i, n+1, i):
                not_prime[j] = 1
    return prime

t = int(input())
n = [int(input()) for _ in range(t)]
x = max(n)
prime = get_prime(x)

dp = [0] * (x + 1)
dp[0] = dp[1] = 0
for i in range(2, x + 1):
    if i in prime:
        dp[i] = 1
    else:
        for j in prime:
            if j > i:
                break
            if dp[i-j] == 0:
                dp[i] = 1
                break

for i in n:
    print(dp[i])
